#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>

using namespace std;

// 2653. 滑动子数组的美丽值
// https://leetcode.cn/problems/sliding-subarray-beauty/

class Solution1 {
public:
    vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {
        vector<int> ans;
        multiset<int> recordNum;
        int left = 0;
        for (int i = 0; i < nums.size(); i++){
            recordNum.insert(nums[i]);
            if (i + left + 1 < k)
            {
                continue;
            }
            auto it = recordNum.begin();
            advance(it, x - 1);
            int curX = *it;
            ans.push_back(curX < 0 ? curX : 0);

            auto target = recordNum.find(nums[left]);
            recordNum.erase(target);
            left++;
        }
        return ans;
    }
};

class Solution {
public:
    vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {
        map<int, int> recordNumberCount;
        int left = 0;
        vector<int> ans;
        for (int i = 0; i < nums.size(); i++)
        {
            recordNumberCount[nums[i]]++;
            if(i - left + 1 < k){
                continue;
            }
            // 找第x小的数
            int sum = 0;
            int curTarget = 0;
            for (auto it : recordNumberCount)
            {
                sum += it.second;
                if(sum >= x){
                    curTarget = it.first;
                    break;
                }
            }
            ans.push_back(curTarget < 0 ? curTarget : 0);
            recordNumberCount[nums[left]]--;
            left++;
        }
        return ans;
    }
};

int main()
{
    return 0;
}